package com.salim.leetcode.$54;

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if(matrix.length==0){
            return result;
        }
        int count = 0;
        int rowLength = matrix[0].length;
        int colLength = matrix.length;
        boolean[][] walked = new boolean[colLength][rowLength];
        int position = 0;
        int i=0;
        int j=0;
        while (count<rowLength*colLength){
            //右
            if(position%4==0){
                position++;
                while (j<rowLength && !walked[i][j]){
                    walked[i][j] = true;
                    result.add(matrix[i][j]);
                    j++;
                    count++;
                }
                j--;
                i++;
            }
            //下
            if(position%4==1){
                position++;
                while (i<colLength && !walked[i][j]){
                    walked[i][j] = true;
                    result.add(matrix[i][j]);
                    i++;
                    count++;
                }
                i--;
                j--;
            }
            //左
            if(position%4==2){
                position++;
                while (j>=0 && !walked[i][j]){
                    walked[i][j] = true;
                    result.add(matrix[i][j]);
                    j--;
                    count++;
                }
                j++;
                i--;
            }
            //上
            if(position%4==3){
                position++;
                while (i>=0 && !walked[i][j]){
                    walked[i][j] = true;
                    result.add(matrix[i][j]);
                    i--;
                    count++;
                }
                i++;
                j++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        SpiralMatrix s = new SpiralMatrix();
        s.spiralOrder(new int[][]{{1, 2, 3, 4},{5,6,7,8},{9,10,11,12}});
    }
}
